{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #单词替换"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #trie #array #hash-table #string"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #字典树 #数组 #哈希表 #字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: replaceWords"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #单词替换"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>在英语中，有一个叫做&nbsp;<code>词根(root)</code> 的概念，它可以跟着其他一些词组成另一个较长的单词&mdash;&mdash;我们称这个词为&nbsp;<code>继承词(successor)</code>。例如，词根<code>an</code>，跟随着单词&nbsp;<code>other</code>(其他)，可以形成新的单词&nbsp;<code>another</code>(另一个)。</p>\n",
    "\n",
    "<p>现在，给定一个由许多词根组成的词典和一个句子，需要将句子中的所有<code>继承词</code>用<code>词根</code>替换掉。如果<code>继承词</code>有许多可以形成它的<code>词根</code>，则用最短的词根替换它。</p>\n",
    "\n",
    "<p>需要输出替换之后的句子。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>dictionary = [&quot;cat&quot;,&quot;bat&quot;,&quot;rat&quot;], sentence = &quot;the cattle was rattled by the battery&quot;\n",
    "<strong>输出：</strong>&quot;the cat was rat by the bat&quot;\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>dictionary = [&quot;a&quot;,&quot;b&quot;,&quot;c&quot;], sentence = &quot;aadsfasf absbs bbab cadsfafs&quot;\n",
    "<strong>输出：</strong>&quot;a a b c&quot;\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>dictionary = [&quot;a&quot;, &quot;aa&quot;, &quot;aaa&quot;, &quot;aaaa&quot;], sentence = &quot;a aa a aaaa aaa aaa aaa aaaaaa bbb baba ababa&quot;\n",
    "<strong>输出：</strong>&quot;a a a a a a a a bbb baba a&quot;\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 4：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>dictionary = [&quot;catt&quot;,&quot;cat&quot;,&quot;bat&quot;,&quot;rat&quot;], sentence = &quot;the cattle was rattled by the battery&quot;\n",
    "<strong>输出：</strong>&quot;the cat was rat by the bat&quot;\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 5：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>dictionary = [&quot;ac&quot;,&quot;ab&quot;], sentence = &quot;it is abnormal that this solution is accepted&quot;\n",
    "<strong>输出：</strong>&quot;it is ab that this solution is ac&quot;\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= dictionary.length&nbsp;&lt;= 1000</code></li>\n",
    "\t<li><code>1 &lt;= dictionary[i].length &lt;= 100</code></li>\n",
    "\t<li><code>dictionary[i]</code>&nbsp;仅由小写字母组成。</li>\n",
    "\t<li><code>1 &lt;= sentence.length &lt;= 10^6</code></li>\n",
    "\t<li><code>sentence</code>&nbsp;仅由小写字母和空格组成。</li>\n",
    "\t<li><code>sentence</code> 中单词的总量在范围 <code>[1, 1000]</code> 内。</li>\n",
    "\t<li><code>sentence</code> 中每个单词的长度在范围 <code>[1, 1000]</code> 内。</li>\n",
    "\t<li><code>sentence</code> 中单词之间由一个空格隔开。</li>\n",
    "\t<li><code>sentence</code>&nbsp;没有前导或尾随空格。</li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><meta charset=\"UTF-8\" />注意：本题与主站 648&nbsp;题相同：&nbsp;<a href=\"https://leetcode-cn.com/problems/replace-words/\">https://leetcode-cn.com/problems/replace-words/</a></p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [UhWRSj](https://leetcode.cn/problems/UhWRSj/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [UhWRSj](https://leetcode.cn/problems/UhWRSj/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[\"cat\",\"bat\",\"rat\"]\\n\"the cattle was rattled by the battery\"', '[\"a\",\"b\",\"c\"]\\n\"aadsfasf absbs bbab cadsfafs\"', '[\"a\", \"aa\", \"aaa\", \"aaaa\"]\\n\"a aa a aaaa aaa aaa aaa aaaaaa bbb baba ababa\"', '[\"catt\",\"cat\",\"bat\",\"rat\"]\\n\"the cattle was rattled by the battery\"', '[\"ac\",\"ab\"]\\n\"it is abnormal that this solution is accepted\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def replaceWords(self, dictionary: List[str], sentence: str) -> str:\n",
    "        mylist = sentence.split(\" \")\n",
    "        for i in range(len(mylist)):\n",
    "            mylist0 = []\n",
    "            count = []\n",
    "            for c in dictionary:\n",
    "                s = len(c)\n",
    "                if mylist[i][0:s] == c:\n",
    "                    mylist0.append(c)\n",
    "                    count.append(s)\n",
    "            if len(count) != 0:\n",
    "                COUNT = min(count)\n",
    "                for x in mylist0:\n",
    "                    if len(x) == COUNT:\n",
    "                        mylist[i] = x\n",
    "        return \" \".join(mylist)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def replaceWords(self, dictionary: List[str], sentence: str) -> str:\n",
    "        words = sentence.split(' ')\n",
    "\n",
    "        for i, word in enumerate(words):\n",
    "            for root in dictionary:\n",
    "                if word[: len(root)] == root:\n",
    "                    words[i] = root\n",
    "                    word = root\n",
    "        \n",
    "        return \" \".join(words)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def replaceWords(self, dictionary: List[str], sentence: str) -> str:\n",
    "        dictionarySet = set(dictionary)\n",
    "        words = sentence.split(' ')\n",
    "        for i, word in enumerate(words):\n",
    "            for j in range(1, len(words) + 1):\n",
    "                if word[:j] in dictionarySet:\n",
    "                    words[i] = word[:j]\n",
    "                    break\n",
    "        return ' '.join(words)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def replaceWords(self, dictionary: List[str], sentence: str) -> str:\n",
    "\n",
    "        length, ans = len(dictionary), []\n",
    "        for m in range(length):\n",
    "            pre = dictionary[m]\n",
    "            if pre:\n",
    "                for n in range(m + 1, length):\n",
    "                    if dictionary[n]:\n",
    "                        bck = dictionary[n]\n",
    "                        lp, lb = len(pre), len(bck)\n",
    "                        if lp < lb and bck[:lp] == pre and pre * bck.count(pre) == bck:      \n",
    "                            dictionary[n] = 0\n",
    "\n",
    "\n",
    "\n",
    "                ans.append(pre)\n",
    "\n",
    "        ans = set(ans)\n",
    "         \n",
    "        \n",
    "        res = []\n",
    "        ls = sentence.split(' ')\n",
    "        \n",
    "        for i in range(len(ls)):\n",
    "            f = 1\n",
    "            for j in range(len(ls[i])):\n",
    "                tmp = ls[i][:j+1]\n",
    "                if tmp in ans:\n",
    "                    f = 0\n",
    "                    res.append(tmp)    \n",
    "                    break\n",
    "            if f:\n",
    "                res.append(ls[i])\n",
    "        return ' '.join(res)\n",
    "\n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def replaceWords(self, dictionary: List[str], sentence: str) -> str:\n",
    "        dictionary=set(dictionary)\n",
    "        s=sentence.split(' ')\n",
    "        res=[]\n",
    "        # i,j=0,0\n",
    "        for i in s:\n",
    "            si=''\n",
    "            for j in i:\n",
    "                si+=j\n",
    "                if si in dictionary:\n",
    "                    break\n",
    "            res.append(si)\n",
    "        return ' '.join(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "class Solution:\n",
    "    def replaceWords(self, dictionary: List[str], sentence: str) -> str:\n",
    "        res = []\n",
    "        @lru_cache\n",
    "        def p(ind,s):\n",
    "            if ind == len(s):\n",
    "                return s\n",
    "            if s[:ind] in dictionary:\n",
    "                return s[:ind]\n",
    "            return p(ind+1,s)\n",
    "        s1 = sentence.split(' ')\n",
    "        for j in s1:\n",
    "            res.append(p(1,j))\n",
    "        res = ' '.join(res)\n",
    "        return res\n",
    "        print('res',res)\n",
    "    # @lru_cache\n",
    "    # def p(self,ind,dictionary,s):\n",
    "    #     if ind == len(s):\n",
    "    #         return s\n",
    "    #     if s[:ind] in dictionary:\n",
    "    #         return s[:ind]\n",
    "    #     return self.p(ind+1,dictionary,s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def replaceWords(self, dictionary: List[str], sentence: str) -> str:\n",
    "        dictionary.sort()\n",
    "        flags = [False] * len(sentence)\n",
    "        ans = []\n",
    "        for i, word in enumerate(sentence.split()):\n",
    "            exist_flag = False\n",
    "            for d in dictionary:\n",
    "                if d not in word:\n",
    "                    continue\n",
    "                if not flags[i] and word[:len(d)] == d:\n",
    "                    exist_flag = True\n",
    "                    ans.append(d)\n",
    "                    flags[i] = True\n",
    "                    break\n",
    "            if not exist_flag:\n",
    "                ans.append(word)\n",
    "        return ' '.join(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def replaceWords(self, a: List[str], s: str) -> str:\n",
    "        return re.sub(f\"\\\\b({'|'.join(sorted(a, key=len))})[^ ]+\", r'\\1', s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def replaceWords(self, dictionary: List[str], sentence: str) -> str:\n",
    "        res = []\n",
    "        dictionary = sorted(dictionary, key=lambda x: len(x))\n",
    "        sub_str = '^' + '|^'.join(dictionary)\n",
    "        for i in sentence.split():\n",
    "            temp = re.findall(sub_str, i)\n",
    "            if temp:\n",
    "                res.append(temp[0])\n",
    "            else:\n",
    "                res.append(i)\n",
    "        return ' '.join(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def replaceWords(self, dictionary: List[str], sentence: str) -> str:\n",
    "        # ans = set(dictionary)\n",
    "        f = defaultdict(set)\n",
    "        n = len(dictionary[0])\n",
    "        for i, dic in enumerate(dictionary):\n",
    "            for j in range(1, len(dic) + 1):\n",
    "                f[j].add(dic[:j])\n",
    "            f[dic] = f.get(dic, dic)\n",
    "        # print(f)\n",
    "        words = sentence.split(' ')\n",
    "        for i, word in enumerate(words):\n",
    "            for j in range(1, len(word) + 1):                \n",
    "                if word[:j] not in f[j]:\n",
    "                    break\n",
    "                if word[:j] in f[word[:j]]:\n",
    "                    words[i] = word[:j]\n",
    "                    break\n",
    "                \n",
    "        return ' '.join(words)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    class TreeNode:\n",
    "        def __init__(self, val='', left=None, right=None):\n",
    "            self.val = val\n",
    "            self.left = left\n",
    "            self.right = right\n",
    "\n",
    "    class DictionaryTree:\n",
    "        def __init__(self):\n",
    "            self.roots = [None for _ in range(26)]\n",
    "\n",
    "        def addRootWord(self, root_word: str):\n",
    "            position = ord(root_word[0]) - ord('a')\n",
    "            new_word = False\n",
    "            if self.roots[position] is None:\n",
    "                self.roots[position] = Solution.TreeNode()\n",
    "                new_word = True\n",
    "            index = self.roots[position]\n",
    "            for char in root_word[1:]:\n",
    "                if index.left is None:\n",
    "                    if new_word:\n",
    "                        index.left = Solution.TreeNode(char)\n",
    "                        index = index.left\n",
    "                    else:\n",
    "                        return\n",
    "                else:\n",
    "                    index = index.left\n",
    "                    while index.val != char:\n",
    "                        if index.right is None:\n",
    "                            index.right = Solution.TreeNode(char)\n",
    "                            index = index.right\n",
    "                            new_word = True\n",
    "                            break\n",
    "                        else:\n",
    "                            index = index.right\n",
    "            index.left = None\n",
    "            index.right = None\n",
    "\n",
    "        def getRootWord(self, word: str) -> Optional[str]:\n",
    "            position = ord(word[0]) - ord('a')\n",
    "            if self.roots[position] is None:\n",
    "                return word\n",
    "            else:\n",
    "                index = self.roots[position]\n",
    "                root_word = word[0]\n",
    "                for char in word[1:]:\n",
    "                    if index.left is None:\n",
    "                        return root_word\n",
    "                    else:\n",
    "                        index = index.left\n",
    "                        while index.val != char:\n",
    "                            if index.right is None:\n",
    "                                return word\n",
    "                            else:\n",
    "                                index = index.right\n",
    "                        root_word += index.val\n",
    "\n",
    "                if index.left is None:\n",
    "                    return root_word\n",
    "                else:\n",
    "                    return word\n",
    "\n",
    "    def replaceWords(self, dictionary: List[str], sentence: str) -> str:\n",
    "        dt = Solution.DictionaryTree()\n",
    "        for word in dictionary:\n",
    "            dt.addRootWord(word)\n",
    "\n",
    "        split_words = sentence.split(' ')\n",
    "        return ' '.join([dt.getRootWord(word) for word in split_words])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def replaceWords(self, dictionary: List[str], sentence: str) -> str:\n",
    "        trie = {}\n",
    "        for x in dictionary:\n",
    "            reduce(lambda d, c: d.setdefault(c, {}), x, trie)['!'] = x\n",
    "            \n",
    "        def find(x):\n",
    "            cur = trie\n",
    "            for c in x:\n",
    "                if not c in cur or '!' in cur:\n",
    "                    break\n",
    "                cur = cur[c]\n",
    "            return cur.get('!', x)\n",
    "        return ' '.join(map(find, sentence.split()))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "\n",
    "    def __init__(self):\n",
    "        self.dic = {}\n",
    "\n",
    "    def insert(self, word: str) -> None:\n",
    "        #print(\"word\", word)\n",
    "        dic = self.dic\n",
    "        found = False\n",
    "        for i, s in enumerate(word):\n",
    "            #print(dic, s)\n",
    "            if s in dic:\n",
    "                dic = dic[s]\n",
    "                found = True\n",
    "            else:\n",
    "                if found and not dic:\n",
    "                    print(\"yes\", dic)\n",
    "                    return \n",
    "                dic[s] = {0: 0}\n",
    "                #print(\"here\", dic)\n",
    "                dic = dic[s]\n",
    "        dic.clear()\n",
    "        # print(self.dic)\n",
    "        # print()\n",
    "\n",
    "\n",
    "\n",
    "    # def startsWith(self, prefix: str) -> bool:\n",
    "    #     dic = self.dic\n",
    "    #     found = False\n",
    "    #     for i in prefix:\n",
    "    #         if i in dic:\n",
    "    #             dic = dic[i]\n",
    "    #             found = True\n",
    "    #         else:\n",
    "    #             if not dic and found:\n",
    "    #                 return True\n",
    "    #             return False\n",
    "    #     return True\n",
    "    \n",
    "    def replace(self, prefix: str) -> bool:\n",
    "        dic = self.dic\n",
    "        string = \"\"\n",
    "        for i in prefix:\n",
    "            # print(dic)\n",
    "            # print()\n",
    "            if i in dic:\n",
    "                dic = dic[i]\n",
    "                string += i\n",
    "            else:\n",
    "                if dic:\n",
    "                    return prefix\n",
    "\n",
    "                if string == \"\":\n",
    "                    return prefix\n",
    "                else:\n",
    "                    return string\n",
    "        return string\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def replaceWords(self, dictionary: List[str], sentence: str) -> str:\n",
    "        trie = Trie()\n",
    "        for i in dictionary:\n",
    "            #if not trie.startsWith(i):\n",
    "            trie.insert(i)\n",
    "        \n",
    "        sen = sentence.split()\n",
    "        ans = []\n",
    "        for i in sen:\n",
    "            ans.append(trie.replace(i))\n",
    "        \n",
    "        return \" \".join(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def replaceWords(self, dictionary: List[str], sentence: str) -> str:\n",
    "        trie = {}\n",
    "        for word in dictionary:\n",
    "            cur = trie\n",
    "            for c in word:\n",
    "                if c not in cur:\n",
    "                    cur[c] = {} \n",
    "                cur = cur[c]\n",
    "            cur['#'] = {}\n",
    "        s_list = sentence.split(' ')\n",
    "        for j, s in enumerate(s_list):\n",
    "            cur = trie\n",
    "            for i, c in enumerate(s):\n",
    "                if '#' in cur:\n",
    "                    s_list[j] = s[:i]\n",
    "                    break\n",
    "                if c not in cur:\n",
    "                    break\n",
    "                cur = cur[c]\n",
    "        return ' '.join(s_list)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def replaceWords(self, dictionary: List[str], sentence: str) -> str:\n",
    "\n",
    "        #### self-method\n",
    "        # import collections\n",
    "        # words=sentence.split()\n",
    "\n",
    "        # dictionary.sort()\n",
    "        # hash_ = collections.defaultdict(list)\n",
    "        # for w in dictionary:\n",
    "        #     hash_[len(w)].append(w)\n",
    "\n",
    "        # all_items = []\n",
    "        # for each in hash_:\n",
    "        #     all_items.extend(hash_[each])\n",
    "\n",
    "        # new = []\n",
    "        # for w in words:\n",
    "        #     c=len(new)\n",
    "        #     for item in all_items:\n",
    "        #         if w[:len(item)] == item:\n",
    "        #             new.append(item)\n",
    "        #             break\n",
    "        #     if c==len(new):\n",
    "        #         new.append(w)\n",
    "        # return \" \".join(new)\n",
    "\n",
    "        ## method 1: 对sentence中的每个词遍历字典并替换\n",
    "        # dictionarySet = set(dictionary)\n",
    "        # words = sentence.split(' ')\n",
    "        # for i, word in enumerate(words):\n",
    "        #     for j in range(1, len(words) + 1):\n",
    "        #         if word[:j] in dictionarySet:\n",
    "        #             words[i] = word[:j]\n",
    "        #             break\n",
    "        # return ' '.join(words)\n",
    "\n",
    "        ## method 2: 字典树\n",
    "        trie = dict()\n",
    "        for w in dictionary:\n",
    "            cur=trie\n",
    "            for c in w:\n",
    "                if c not in cur:\n",
    "                    cur[c]=dict()\n",
    "                cur=cur[c]\n",
    "            cur['is_end'] = 1\n",
    "        \n",
    "        words=sentence.split()\n",
    "        for i,word in enumerate(words):\n",
    "            cur = trie\n",
    "            for j,c in enumerate(word):\n",
    "                if 'is_end' in cur:\n",
    "                    words[i] = word[:j]\n",
    "                    break\n",
    "                if c not in cur:\n",
    "                    break\n",
    "                cur = cur[c]\n",
    "        return ' '.join(words)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def replaceWords(self, dictionary: List[str], sentence: str) -> str:\n",
    "        trie = {}\n",
    "        for word in dictionary:\n",
    "            cur = trie\n",
    "            for c in word:\n",
    "                if c not in cur:\n",
    "                    cur[c] = {}\n",
    "                cur = cur[c]\n",
    "            cur['#'] = {}\n",
    "\n",
    "        words = sentence.split(' ')\n",
    "        for i, word in enumerate(words):\n",
    "            cur = trie\n",
    "            for j, c in enumerate(word):\n",
    "                if '#' in cur:\n",
    "                    words[i] = word[:j]\n",
    "                    break\n",
    "                if c not in cur:\n",
    "                    break\n",
    "                cur = cur[c]\n",
    "        return ' '.join(words)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import Optional\n",
    "\n",
    "\n",
    "class Trie:\n",
    "\n",
    "    def __init__(self) -> None:\n",
    "        self.words_info = dict()\n",
    "        self.root_flag = '[END]'\n",
    "\n",
    "    def insert(self, word: str) -> None:\n",
    "        root = self.words_info\n",
    "        for char in word:\n",
    "            if char not in root:\n",
    "                root[char] = dict()\n",
    "            root = root[char]\n",
    "        root[self.root_flag] = 1\n",
    "\n",
    "    def search(self, word: str) -> Optional[str]:\n",
    "        \"\"\"\n",
    "        查找单词的最短前缀，不存在的话，返回None\n",
    "        \"\"\"\n",
    "        root = self.words_info\n",
    "        prefix_chars = []\n",
    "        valid = False\n",
    "        for char in word:\n",
    "            if self.root_flag in root:\n",
    "                valid = True\n",
    "                break\n",
    "            # 注意和上面的检测顺序\n",
    "            if char not in root:\n",
    "                break\n",
    "            prefix_chars.append(char)\n",
    "            root = root[char]\n",
    "        if valid:\n",
    "            return ''.join(prefix_chars)\n",
    "\n",
    "        return None\n",
    "\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def replaceWords(self, dictionary: List[str], sentence: str) -> str:\n",
    "        trie_obj = Trie()\n",
    "        for word in dictionary:\n",
    "            trie_obj.insert(word)\n",
    "\n",
    "        len_sent = len(sentence)\n",
    "        rst = []\n",
    "        word = []\n",
    "        for i in range(len_sent):\n",
    "            if sentence[i] == ' ':\n",
    "                if word:\n",
    "                    word = ''.join(word)\n",
    "                    prefix = trie_obj.search(word)\n",
    "                    prefix = word if prefix is None else prefix\n",
    "                    rst.append(prefix)\n",
    "                word = []\n",
    "            else:\n",
    "                word.append(sentence[i])\n",
    "        if word:\n",
    "            word = ''.join(word)\n",
    "            prefix = trie_obj.search(word)\n",
    "            prefix = word if prefix is None else prefix\n",
    "            rst.append(prefix)\n",
    "        return ' '.join(rst)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "\n",
    "    def __init__(self):\n",
    "        self.tree = {}\n",
    "\n",
    "    #插入字符，需要判断一下字典内是否已经有该字符的词根\n",
    "    def insert(self, word: str) -> None:\n",
    "        cur = self.tree\n",
    "        for i in range(len(word)):\n",
    "            if word[i] in cur:  \n",
    "                cur = cur[word[i]]\n",
    "                if '%' in cur: return  #已经存在词根\n",
    "            else:\n",
    "                cur[word[i]] = {}\n",
    "                cur = cur[word[i]]\n",
    "        cur['%'] = True  #有效词根\n",
    "\n",
    "    #找到单词的词根，如果无词根则返回单词\n",
    "    def findPrefix(self, word):  \n",
    "        cur = self.tree\n",
    "        for i in range(len(word)):\n",
    "            if word[i] in cur:\n",
    "                cur = cur[word[i]]\n",
    "            else: #不在cur中，判断当前是否是有效词根\n",
    "                return word[:i] if '%' in cur else word\n",
    "        return word #遍历完了，不用管了，直接返回word\n",
    "\n",
    "class Solution:\n",
    "    def replaceWords(self, dictionary: List[str], sentence: str) -> str:\n",
    "        trie = Trie()\n",
    "        dictionary.sort(key = len)  #词根一定比单词长度短，所以需要从短到长遍历\n",
    "        for word in dictionary:\n",
    "            trie.insert(word)\n",
    "        ans = []\n",
    "        sentence = sentence.split()\n",
    "        for word in sentence:\n",
    "            ans.append(trie.findPrefix(word))\n",
    "        return ' '.join(ans)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def replaceWords(self, dictionary: List[str], sentence: str) -> str:\n",
    "        tree = {}\n",
    "        for word in dictionary:\n",
    "            if not word:\n",
    "                continue\n",
    "            cur = tree\n",
    "            for i in word:\n",
    "                cur = cur.setdefault(i,{})\n",
    "            cur[\"#\"] = \"#\"\n",
    "    \n",
    "        words = sentence.split()\n",
    "        print(words)\n",
    "        re = []\n",
    "        for word in words:\n",
    "            cur = tree\n",
    "            for i,j in enumerate(word):\n",
    "                if \"#\" in cur:\n",
    "                    re.append(word[:i])\n",
    "                    break\n",
    "                if j not in cur:\n",
    "                    re.append(word)\n",
    "                    break \n",
    "                if i == len(word) - 1:\n",
    "                    re.append(word)\n",
    "                    break\n",
    "                \n",
    "                cur = cur[j]\n",
    "        print(re)\n",
    "        return \" \".join(re)\n",
    "\n",
    "                \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def replaceWords(self, dictionary: List[str], sentence: str) -> str:\n",
    "        trie = {}\n",
    "        # 构造字典树\n",
    "        for w in dictionary:\n",
    "            cur = trie\n",
    "            for c in w:\n",
    "                if c not in cur:\n",
    "                    cur[c] = {}\n",
    "                cur = cur[c]\n",
    "            cur[\"#\"] = {}\n",
    "    \n",
    "        words = sentence.split(\" \")\n",
    "        for i,word in enumerate(words):\n",
    "            cur = trie\n",
    "            for j,c in enumerate(word):\n",
    "                if \"#\" in cur:\n",
    "                    words[i] = word[:j]\n",
    "                    break           \n",
    "                if c not in cur:\n",
    "                    break\n",
    "                cur = cur[c]\n",
    "        return \" \".join(words)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def replaceWords(self, dictionary: List[str], sentence: str) -> str:\n",
    "        trie = {}\n",
    "\n",
    "        for w in dictionary:\n",
    "            p = trie\n",
    "            for c in w:\n",
    "                if c not in p:\n",
    "                    p[c] = {}\n",
    "\n",
    "                p = p[c]\n",
    "\n",
    "            p['$'] = {}\n",
    "\n",
    "        ret = []\n",
    "        for w in sentence.split(' '):\n",
    "            p = trie\n",
    "            for i in range(len(w)):\n",
    "                c = w[i]\n",
    "                if c in p:\n",
    "                    p = p[c]\n",
    "\n",
    "                    if '$' in p:\n",
    "                        ret.append(w[:i + 1])\n",
    "                        break\n",
    "                else:\n",
    "                    ret.append(w)\n",
    "                    break\n",
    "            else:\n",
    "                ret.append(w)\n",
    "\n",
    "        return ' '.join(ret)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self):\n",
    "        self.root = {}\n",
    "    def insert(self, word):\n",
    "        node = self.root\n",
    "        for char in word+\"#\":\n",
    "            if char not in node:\n",
    "                node[char] = {}\n",
    "            node = node[char]\n",
    "    def find(self,word):\n",
    "        node = self.root\n",
    "        for i in range(len(word)):\n",
    "            if word[i] in node:\n",
    "                node = node[word[i]]\n",
    "            else:\n",
    "                return False\n",
    "        return \"#\" in node\n",
    "    def find_prefix(self, word):\n",
    "        node = self.root\n",
    "        for i in range(len(word)):\n",
    "            if \"#\" in node:\n",
    "                return word[:i]\n",
    "            if word[i] in node:\n",
    "                node = node[word[i]]\n",
    "            else:\n",
    "                break\n",
    "        return word\n",
    "\n",
    "class Solution:\n",
    "    def replaceWords(self, dictionary: List[str], sentence: str) -> str:\n",
    "        trie = Trie()\n",
    "        for d in dictionary:\n",
    "            trie.insert(d)\n",
    "        words = sentence.split(\" \")\n",
    "        return \" \".join(trie.find_prefix(word) for word in words)  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def replaceWords(self, dictionary: List[str], sentence: str) -> str:\n",
    "        trie = {}\n",
    "        for d in dictionary:\n",
    "            cur_dict = trie\n",
    "            for i in range(len(d)):\n",
    "                if d[i] not in cur_dict:\n",
    "                    cur_dict[d[i]] = {}\n",
    "                cur_dict = cur_dict[d[i]]\n",
    "            cur_dict['#'] = True\n",
    "        print(trie)\n",
    "\n",
    "        stens = sentence.split(' ')\n",
    "        for i in range(len(stens)):\n",
    "            sten = stens[i]\n",
    "            cur = ''\n",
    "            pointer = trie\n",
    "            for s in sten:\n",
    "                if pointer.get('#', False):\n",
    "                    stens[i] = cur[:]\n",
    "                    break\n",
    "\n",
    "                if s in pointer:\n",
    "                    \n",
    "                    cur += s\n",
    "                    pointer = pointer[s]\n",
    "                else:\n",
    "                    break\n",
    "        \n",
    "        print(' '.join(stens))\n",
    "        return ' '.join(stens)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def replaceWords(self, dictionary: List[str], sentence: str) -> str:\n",
    "        dict = {}\n",
    "        for i in dictionary:\n",
    "            root = dict\n",
    "            parent = None\n",
    "            for j in i:\n",
    "                if j not in root: root[j] = {}\n",
    "                if root[j] is None:\n",
    "                    parent = None\n",
    "                    break\n",
    "                parent = root\n",
    "                root = root[j]\n",
    "            if parent:\n",
    "                parent[i[-1]] = None\n",
    "        arr = sentence.split()\n",
    "        ret = []\n",
    "        for i in arr:\n",
    "            root = dict\n",
    "            ret.append([])\n",
    "            for j in range(len(i)):\n",
    "                if root is None:\n",
    "                    break\n",
    "                if i[j] in root:\n",
    "                    root = root[i[j]]\n",
    "                    ret[-1].append(i[j])\n",
    "                else:\n",
    "                    ret[-1].append(i[j:])\n",
    "                    break\n",
    "\n",
    "        return ' '.join(''.join(x) for x in ret)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.root = collections.defaultdict(dict)\n",
    "\n",
    "    def replaceWords(self, dictionary: List[str], sentence: str) -> str:\n",
    "        # 构建一个前缀树\n",
    "        for word in dictionary:\n",
    "            self.insert(word)\n",
    "        # 依次判断句子中每个词的前面的部分是否与dictionary有重合\n",
    "        list1 = sentence.split(\" \")\n",
    "        res = []\n",
    "        for jj in list1:\n",
    "            temp = self.search(jj)\n",
    "            if temp:\n",
    "                res.append(temp)\n",
    "            else:\n",
    "                res.append(jj)\n",
    "        return ' '.join(res)\n",
    "        \n",
    "    def insert(self, word: str) -> None:#前缀树的插入构建\n",
    "        nownode = self.root\n",
    "        for s in word:\n",
    "            if s not in nownode.keys():\n",
    "                nownode[s] = collections.defaultdict(dict)  #创建下一个节点\n",
    "            nownode = nownode[s]\n",
    "        nownode['#']='#'         #有一定的局限性 前提是单词里不能有结束符\n",
    "\n",
    "    def search(self, word: str) -> bool:#前缀树的搜索\n",
    "        nownode = self.root\n",
    "        path = ''\n",
    "        for s in word:\n",
    "            if s in nownode.keys():\n",
    "                path+=s\n",
    "                nownode = nownode[s]\n",
    "                if '#' in nownode.keys():#当碰到一个结束符的时候，说明找到了一个前缀(词根)\n",
    "                    return path\n",
    "            else:\n",
    "                return False\n",
    "       \n",
    "\n",
    "# #暴力解\n",
    "# class Solution:\n",
    "#     def replaceWords(self, dictionary: List[str], sentence: str) -> str:\n",
    "#         dictionary = set(dictionary)\n",
    "#         list1 = sentence.split(\" \")\n",
    "#         for i in range(len(list1)):\n",
    "#             for j in range(len(list1[i])):\n",
    "#                 if list1[i][:j] in dictionary:\n",
    "#                     list1[i] = list1[i][:j]\n",
    "#                     break\n",
    "#         return \" \".join(list1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    class Trie:\n",
    "        __slots__ = ['next', 'isEnd']\n",
    "        def __init__(self):\n",
    "            self.next = defaultdict(Solution.Trie)\n",
    "            self.isEnd = None\n",
    "\n",
    "    def addWord(self, head, word):\n",
    "        for i in word:\n",
    "            head = head.next[i]\n",
    "        head.isEnd = word\n",
    "\n",
    "    def replaceWords(self, dictionary: List[str], sentence: str) -> str:\n",
    "        head = self.Trie()\n",
    "        for i in dictionary:\n",
    "            self.addWord(head, i)\n",
    "        sentence = sentence.split()\n",
    "        for i in range(len(sentence)):\n",
    "            curr = head\n",
    "            for c in sentence[i]:\n",
    "                curr = curr.next.get(c, None)\n",
    "                if curr is None or curr.isEnd:\n",
    "                    break\n",
    "            if curr and curr.isEnd:\n",
    "                sentence[i] = curr.isEnd\n",
    "        return ' '.join(sentence)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def replaceWords(self, dictionary: List[str], sentence: str) -> str:\n",
    "        root = [{}, False]\n",
    "\n",
    "        for word in dictionary:\n",
    "            curr = root\n",
    "            for s in word:\n",
    "                if not s in curr[0]:\n",
    "                    curr[0][s] = [{}, False]\n",
    "                curr = curr[0][s]\n",
    "            curr[1] = True\n",
    "\n",
    "        sentence = sentence.split(' ')\n",
    "        for i, word in enumerate(sentence):            \n",
    "            \n",
    "            curr = root\n",
    "            replace = ''\n",
    "            for s in word:\n",
    "                if s in curr[0]:\n",
    "                    replace += s\n",
    "                    if curr[0][s][1]: \n",
    "                        break\n",
    "                    else: \n",
    "                        curr = curr[0][s]\n",
    "                else:\n",
    "                    replace = ''\n",
    "                    break\n",
    "\n",
    "            if replace != '':\n",
    "                sentence[i] = replace\n",
    "        \n",
    "        return ' '.join(sentence)\n",
    "            \n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def replaceWords(self, dictionary: List[str], sentence: str) -> str:\n",
    "        root = [{}, False]\n",
    "\n",
    "        for word in dictionary:\n",
    "            curr = root\n",
    "            for s in word:\n",
    "                if not s in curr[0]:\n",
    "                    curr[0][s] = [{}, False]\n",
    "                curr = curr[0][s]\n",
    "            curr[1] = True\n",
    "\n",
    "        sentence = sentence.split(' ')\n",
    "        for i, word in enumerate(sentence):            \n",
    "            \n",
    "            curr = root\n",
    "            replace = ''\n",
    "            for s in word:\n",
    "                if s in curr[0]:\n",
    "                    replace += s\n",
    "                    if curr[0][s][1]: \n",
    "                        break\n",
    "                    else: \n",
    "                        curr = curr[0][s]\n",
    "                else:\n",
    "                    replace = ''\n",
    "                    break\n",
    "            # if not curr[1]:\n",
    "            #     replace = ''\n",
    "\n",
    "            if replace != '':\n",
    "                sentence[i] = replace\n",
    "        \n",
    "        return ' '.join(sentence)\n",
    "            \n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def replaceWords(self, dictionary: List[str], sentence: str) -> str:\n",
    "\n",
    "        prefix = dict()\n",
    "        for word in dictionary:\n",
    "            pre = prefix\n",
    "            for c in word[:-1]:\n",
    "                if c not in pre:\n",
    "                    pre[c] = [{}, False]\n",
    "                pre = pre[c][0]\n",
    "            if word[-1] in pre:\n",
    "                pre[word[-1]][1] = True\n",
    "            else:\n",
    "                pre[word[-1]] = [{}, True]\n",
    "\n",
    "        ans = []\n",
    "        ss = sentence.split(\" \")\n",
    "        for s in ss:\n",
    "            pre = prefix\n",
    "            found = False\n",
    "            for i, c in enumerate(s):\n",
    "                if c not in pre:\n",
    "                    ans.append(s)\n",
    "                    found = True\n",
    "                    break\n",
    "                else:\n",
    "                    if pre[c][1]:\n",
    "                        ans.append(s[:i+1])\n",
    "                        found = True\n",
    "                        break\n",
    "                    else:\n",
    "                        pre = pre[c][0]\n",
    "            if not found:\n",
    "                ans.append(s)\n",
    "        return \" \".join(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "    __slots__ = 'children', 'root'\n",
    "    def __init__(self):\n",
    "        self.children = defaultdict(Trie)\n",
    "        self.root = ''\n",
    "\n",
    "    def insert(self, word):\n",
    "        cur = self\n",
    "        for ch in word:\n",
    "            cur = cur.children[ch]\n",
    "        cur.root = word\n",
    "\n",
    "    def query(self, word):\n",
    "        cur = self\n",
    "        for ch in word:\n",
    "            if ch not in cur.children:\n",
    "                return word\n",
    "            cur = cur.children[ch]\n",
    "            if cur.root:\n",
    "                return cur.root\n",
    "        return word\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def replaceWords(self, dictionary: List[str], sentence: str) -> str:\n",
    "        root = Trie()\n",
    "        for word in dictionary:\n",
    "            root.insert(word)\n",
    "        \n",
    "        ans = []\n",
    "        for word in sentence.split():\n",
    "            ans.append(root.query(word))\n",
    "        return ' '.join(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def replaceWords(self, dictionary: List[str], sentence: str) -> str:\n",
    "        dict_tree = {}\n",
    "        for root in dictionary:\n",
    "            node = dict_tree\n",
    "            for char in root:\n",
    "                if char not in node:\n",
    "                    node[char] = {}\n",
    "                node = node[char]\n",
    "            node[\"#\"] = True\n",
    "\n",
    "        # 对每个单词找到词根\n",
    "        words = sentence.split()\n",
    "        ans = []\n",
    "        for word in words:\n",
    "            node = dict_tree\n",
    "            copy = False\n",
    "            for char in word:\n",
    "                if copy:\n",
    "                    ans.append(char)\n",
    "                    continue\n",
    "                if \"#\" in node:\n",
    "                    ans.append(\" \")\n",
    "                    break\n",
    "                else:\n",
    "                    if char in node:\n",
    "                        node = node[char]\n",
    "                        ans.append(char)\n",
    "                    else:\n",
    "                        copy = True\n",
    "                        ans.append(char)\n",
    "            else:\n",
    "                ans.append(\" \")\n",
    "        return \"\".join(ans)[:-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def replaceWords(self, dictionary: List[str], sentence: str) -> str:\n",
    "        tree = [{}, False]\n",
    "        for w in dictionary:\n",
    "            curr = tree\n",
    "            for s in w:\n",
    "                if s not in curr[0]:\n",
    "                    curr[0][s] = [{}, False]\n",
    "                curr = curr[0][s]\n",
    "            curr[1] = True\n",
    "        \n",
    "        res = []\n",
    "        for w in sentence.split(' '):\n",
    "            curr = tree\n",
    "            trans = \"\"\n",
    "            for s in w:\n",
    "                if curr[1]:\n",
    "                    break\n",
    "                if s not in curr[0]:\n",
    "                    trans = w\n",
    "                    break\n",
    "                else:\n",
    "                    trans += s\n",
    "                    curr = curr[0][s]\n",
    "            if not curr[1]:\n",
    "                trans = w\n",
    "            res.append(trans)\n",
    "        \n",
    "        return ' '.join(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class TreeNode:\n",
    "    def __init__(self, root_name , is_root = False) :\n",
    "        self.val = root_name\n",
    "        self.nextvalue = []\n",
    "        self.nextnode = []\n",
    "        self.check = is_root\n",
    "        \n",
    "class Solution:\n",
    "    def replaceWords(self, dictionary: List[str], sentence: str) -> str:\n",
    "        root = TreeNode('#')\n",
    "        for s_sen in dictionary :\n",
    "            set_root = root\n",
    "            for i, c_sen in enumerate(s_sen) :\n",
    "                if c_sen in set_root.nextvalue :\n",
    "                    set_root = set_root.nextnode[set_root.nextvalue.index(c_sen)]\n",
    "                else :\n",
    "                    add_node = TreeNode(c_sen)\n",
    "                    set_root.nextnode.append(add_node)\n",
    "                    set_root.nextvalue.append(c_sen)\n",
    "                    set_root = add_node\n",
    "                if i == len(s_sen) - 1 :\n",
    "                    set_root.check = True\n",
    "        list_sence = sentence.split(' ')\n",
    "        for j, s_sen in enumerate(list_sence) :\n",
    "            set_root = root\n",
    "            p_list = []\n",
    "            b_check = False\n",
    "            for i, c_sen in enumerate(s_sen) :\n",
    "                if c_sen in set_root.nextvalue :\n",
    "                    p_list.append(c_sen)\n",
    "                    if set_root.nextnode[set_root.nextvalue.index(c_sen)].check == True :\n",
    "                        b_check = True\n",
    "                        break\n",
    "                    set_root = set_root.nextnode[set_root.nextvalue.index(c_sen)]\n",
    "                else :\n",
    "                    break\n",
    "            if b_check :\n",
    "                list_sence[j] = ''.join(p_list)\n",
    "        return ' '.join(list_sence)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def replaceWords(self, dictionary: List[str], sentence: str) -> str:\n",
    "        root = [{}, False]\n",
    "        for word in dictionary:\n",
    "            curr = root\n",
    "            for c in word:\n",
    "                if c not in curr[0]:\n",
    "                    curr[0][c] = [{}, False]\n",
    "                curr = curr[0][c]\n",
    "            curr[1] = True\n",
    "        \n",
    "        res = []\n",
    "        for word in sentence.split(' '):\n",
    "            curr, pres = root, ''\n",
    "            for i, c in enumerate(word):\n",
    "                if curr[1]:\n",
    "                    break\n",
    "                if c in curr[0]:\n",
    "                    pres += c\n",
    "                    curr = curr[0][c]\n",
    "                else:\n",
    "                    pres += word[i:]\n",
    "                    break\n",
    "            res.append(pres)\n",
    "\n",
    "        return ' '.join(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def replaceWords(self, dictionary: List[str], sentence: str) -> str:\n",
    "        root = {}\n",
    "        for word in dictionary:\n",
    "            curNode = root\n",
    "            for i, c in enumerate(word):\n",
    "                if c in curNode:\n",
    "                    if i == len(word) - 1:\n",
    "                        curNode[c][1] = True\n",
    "                    curNode = curNode[c][0]\n",
    "                else:\n",
    "                    curNode[c] = [{}, False]\n",
    "                    if i == len(word) - 1:\n",
    "                        curNode[c][1] = True\n",
    "                    curNode = curNode[c][0]\n",
    "        \n",
    "        ans = \"\"\n",
    "        for word in sentence.split(\" \"):\n",
    "            temp = \"\"\n",
    "            curNode = root\n",
    "            for i, c in enumerate(word):\n",
    "                temp += c\n",
    "                if c in curNode:\n",
    "                    if curNode[c][1] == True:\n",
    "                        ans = ans + \" \" + temp\n",
    "                        break\n",
    "                    else:\n",
    "                        if i == len(word) - 1:\n",
    "                            ans = ans + \" \" + word\n",
    "                            break\n",
    "                        curNode = curNode[c][0]\n",
    "                else:\n",
    "                    ans = ans + \" \" + word\n",
    "                    break\n",
    "        return ans[1:]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def replaceWords(self, dictionary: List[str], sentence: str) -> str:\n",
    "        # 建立前缀树\n",
    "        N = 100009  # 直接设置trie的最大节点\n",
    "        index = 0  # 使用index 来自增记录我们到底用了多少个格子（相当于给被用到格子进行编号）。\n",
    "        trie = [None for _ in range(N)]  # 使用二维数组 trie[]来当作前缀树\n",
    "        trie[0] = [0 for _ in range(26)]\n",
    "        tail_count = [0 for _ in range(N)]  # 使用 tail_count[] 数组记录某个格子被「被标记为结尾的次数」（当 idx 编号的格子被标记了 n 次，则有 tail_count[idx] = n）。\n",
    "        for word in dictionary:\n",
    "            p = 0  # 位置，每次都从0开始\n",
    "            for i in range(len(word)):\n",
    "                c = ord(word[i]) - ord('a')\n",
    "                if trie[p][c] == 0:\n",
    "                    index += 1\n",
    "                    trie[p][c] = index\n",
    "                    trie[index] = [0 for _ in range(26)]\n",
    "                p = trie[p][c]\n",
    "            tail_count[p] += 1\n",
    "        # 使用前缀树\n",
    "        new_sentence = []\n",
    "        for word in sentence.split():\n",
    "            p = 0\n",
    "            cnt = 0\n",
    "            for ch in word:\n",
    "                c = ord(ch) - ord('a')\n",
    "                if trie[p][c] == 0:\n",
    "                    break\n",
    "                cnt += 1\n",
    "                p = trie[p][c]\n",
    "                if tail_count[p]:\n",
    "                    word = word[:cnt]\n",
    "                    break\n",
    "            if word:\n",
    "                new_sentence.append(word)\n",
    "        return ' '.join(new_sentence)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def replaceWords(self, dictionary: List[str], sentence: str) -> str:\n",
    "        # 建立前缀树\n",
    "        N = 100009  # 直接设置trie的最大节点\n",
    "        index = 0  # 使用index 来自增记录我们到底用了多少个格子（相当于给被用到格子进行编号）。\n",
    "        trie = [None for _ in range(N)]  # 使用二维数组 trie[]来当作前缀树\n",
    "        trie[0] = [0 for _ in range(26)]\n",
    "        tail_count = [0 for _ in range(N)]  # 使用 tail_count[] 数组记录某个格子被「被标记为结尾的次数」（当 idx 编号的格子被标记了 n 次，则有 tail_count[idx] = n）。\n",
    "        for word in dictionary:\n",
    "            p = 0  # 位置，每次都从0开始\n",
    "            for i in range(len(word)):\n",
    "                c = ord(word[i]) - ord('a')\n",
    "                if trie[p][c] == 0:\n",
    "                    index += 1\n",
    "                    trie[p][c] = index\n",
    "                    trie[index] = [0 for _ in range(26)]\n",
    "                p = trie[p][c]\n",
    "            tail_count[p] += 1\n",
    "        # 使用前缀树\n",
    "        new_sentence = []\n",
    "        for word in sentence.split():\n",
    "            p = 0\n",
    "            cnt = 0\n",
    "            for ch in word:\n",
    "                c = ord(ch) - ord('a')\n",
    "                if trie[p][c] == 0:\n",
    "                    break\n",
    "                cnt += 1\n",
    "                p = trie[p][c]\n",
    "                if tail_count[p]:\n",
    "                    word = word[:cnt]\n",
    "                    break\n",
    "            if word:\n",
    "                new_sentence.append(word)\n",
    "        return ' '.join(new_sentence)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trier(dict):\n",
    "    def __init__(self):\n",
    "        super(Trier, self).__init__()\n",
    "        self.end = False\n",
    "\n",
    "    def insert(self, prefix):\n",
    "        cur = self\n",
    "        for ch in prefix:\n",
    "            if ch not in cur:\n",
    "                temp = Trier()\n",
    "                cur[ch] = temp\n",
    "            cur = cur[ch]\n",
    "        cur.end = True\n",
    "\n",
    "    def search(self, word):\n",
    "        cur = self\n",
    "        for i, ch in enumerate(word):\n",
    "            if ch not in cur:\n",
    "                return ''\n",
    "            cur = cur[ch]\n",
    "            if cur.end:\n",
    "                return word[:i+1]\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def replaceWords(self, dictionary: List[str], sentence: str) -> str:\n",
    "        dict_tree = Trier()\n",
    "        for word in dictionary:\n",
    "            dict_tree.insert(word)\n",
    "        ans = []\n",
    "        for word in sentence.split():\n",
    "            prefix = dict_tree.search(word)\n",
    "            res = word if not prefix else prefix\n",
    "            ans.append(res)\n",
    "        return \" \".join(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Node:\n",
    "    def __init__(self, isWord=False):\n",
    "        self.child = dict()\n",
    "        self.isWord = isWord\n",
    "\n",
    "class Trie:\n",
    "\n",
    "    def __init__(self):\n",
    "        \"\"\"\n",
    "        Initialize your data structure here.\n",
    "        \"\"\"\n",
    "        self.root = Node()\n",
    "\n",
    "\n",
    "    def insert(self, word: str) -> None:\n",
    "        \"\"\"\n",
    "        Inserts a word into the trie.\n",
    "        \"\"\"\n",
    "        cur = self.root\n",
    "        for x in word:\n",
    "            if x not in cur.child:\n",
    "                cur.child[x] = Node()\n",
    "            cur = cur.child[x]\n",
    "        cur.isWord = True\n",
    "\n",
    "\n",
    "    def search(self, word: str) -> bool:\n",
    "        \"\"\"\n",
    "        Returns if the word is in the trie.\n",
    "        \"\"\"\n",
    "        cur = self.root\n",
    "        for x in word:\n",
    "            if x not in cur.child:\n",
    "                return False\n",
    "            cur = cur.child[x]\n",
    "        return cur.isWord\n",
    "\n",
    "\n",
    "    def startsWith(self, prefix: str) -> bool:\n",
    "        \"\"\"\n",
    "        Returns if there is any word in the trie that starts with the given prefix.\n",
    "        \"\"\"\n",
    "        cur = self.root\n",
    "        for x in prefix:\n",
    "            if x not in cur.child:\n",
    "                return False\n",
    "            cur = cur.child[x]\n",
    "        return True\n",
    "\n",
    "    def getRoot(self, word: str) -> None:\n",
    "        \"\"\"\n",
    "        Inserts a word into the trie.\n",
    "        \"\"\"\n",
    "        cur = self.root\n",
    "        for i, x in enumerate(word):\n",
    "            if x not in cur.child:\n",
    "                return word\n",
    "            cur = cur.child[x]\n",
    "            if cur.isWord:\n",
    "                return word[:i+1]\n",
    "        return word\n",
    "\n",
    "\n",
    "# Your Trie object will be instantiated and called as such:\n",
    "# obj = Trie()\n",
    "# obj.insert(word)\n",
    "# param_2 = obj.search(word)\n",
    "# param_3 = obj.startsWith(prefix)\n",
    "\n",
    "class Solution:\n",
    "    def replaceWords(self, dictionary: List[str], sentence: str) -> str:\n",
    "        tree = Trie()\n",
    "        for word in dictionary:\n",
    "            tree.insert(word)\n",
    "        res = []\n",
    "        for word in sentence.split(\" \"):\n",
    "            res.append(tree.getRoot(word))\n",
    "        return \" \".join(res)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 前缀节点\n",
    "class TrieNode:\n",
    "    def __init__(self):\n",
    "        # 当前节点的子节点，用dict存储，key是字符，value是子节点\n",
    "        self.children = {}\n",
    "        # 当前节点是否是一个单词的结尾\n",
    "        self.is_word = False\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self):\n",
    "        \"\"\"\n",
    "        Initialize your data structure here.\n",
    "        \"\"\"\n",
    "        # 前缀树的根节点\n",
    "        self.root = TrieNode()\n",
    "\n",
    "    def insert(self, word: str) -> None:\n",
    "        \"\"\"\n",
    "        Inserts a word into the trie.\n",
    "        \"\"\"\n",
    "        node = self.root\n",
    "        for c in word:\n",
    "            if c not in node.children:\n",
    "                node.children[c] = TrieNode()\n",
    "            node = node.children[c]\n",
    "        node.is_word = True\n",
    "\n",
    "\n",
    "    def search(self, word: str) -> bool:\n",
    "        \"\"\"\n",
    "        Returns if the word is in the trie.\n",
    "        \"\"\"\n",
    "        node = self.root\n",
    "        for c in word:\n",
    "            if c not in node.children:\n",
    "                return False\n",
    "            node = node.children[c]\n",
    "\n",
    "        return node.is_word\n",
    "\n",
    "\n",
    "    def startsWith(self, prefix: str) -> bool:\n",
    "        \"\"\"\n",
    "        Returns if there is any word in the trie that starts with the given prefix.\n",
    "        \"\"\"\n",
    "        node = self.root\n",
    "        for c in prefix:\n",
    "            if c not in node.children:\n",
    "                return False\n",
    "            node = node.children[c]\n",
    "        return True\n",
    "\n",
    "\n",
    "# 首先将词典中的所有词根插入到前缀树中，然后将句子按照空格分割成单词\n",
    "# 遍历每个单词的每个字符，判断是否存在以该字符结尾的词根。\n",
    "# 如果存在，则将该单词替换为该词根，并继续处理下一个单词。如果不存在，则继续遍历该单词的下一个字符。\n",
    "class Solution:\n",
    "    def replaceWords(self, dictionary: List[str], sentence: str) -> str:\n",
    "        obj = Trie()\n",
    "        for word in dictionary:\n",
    "            obj.insert(word)\n",
    "        words = sentence.split(\" \")\n",
    "        for i in range(len(words)):\n",
    "            for j in range(len(words[i])):\n",
    "                if obj.search(words[i][:j]):\n",
    "                    words[i] = words[i][:j]\n",
    "        return \" \".join(word for word in words)\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Trie:\n",
    "\n",
    "    def __init__(self):\n",
    "        self.children={}\n",
    "        self.isEnd=False\n",
    "    \n",
    "    def insert(self,word):\n",
    "        node=self\n",
    "        for c in word:\n",
    "            if c not in node.children:\n",
    "                node.children[c]=Trie()\n",
    "            node=node.children[c]\n",
    "        node.isEnd=True\n",
    "    \n",
    "    def findRoot(self,word):\n",
    "        node=self\n",
    "        root=[]\n",
    "        for i,c in enumerate(word):\n",
    "            if c not in node.children:\n",
    "                return None\n",
    "            node=node.children[c]\n",
    "            if node.isEnd:\n",
    "                return word[:i+1]\n",
    "        return word[:i+1] if node.isEnd else None\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def replaceWords(self, dictionary: List[str], sentence: str) -> str:\n",
    "        tree=Trie()\n",
    "        for word in dictionary:\n",
    "            tree.insert(word)\n",
    "        words=sentence.split()\n",
    "        ans=[]\n",
    "        for word in words:\n",
    "            root=tree.findRoot(word)\n",
    "            if root:\n",
    "                ans.append(root)\n",
    "            else:\n",
    "                ans.append(word)\n",
    "        return ' '.join(ans)\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self):\n",
    "        self.child = {}\n",
    "        self.isEnd = False\n",
    "    \n",
    "    def add(self, word):\n",
    "        p = self\n",
    "        for c in word:\n",
    "            if c not in p.child:\n",
    "                p.child[c] = Trie()\n",
    "            p = p.child[c]\n",
    "        p.isEnd = True\n",
    "    \n",
    "    def search(self, word):\n",
    "        p = self\n",
    "        for c in word:\n",
    "            if c not in p.child:\n",
    "                return False\n",
    "            p = p.child[c]\n",
    "        return p.isEnd\n",
    "\n",
    "    def matchPrefix(self, word):\n",
    "        p = self\n",
    "        for i, c in enumerate(word):\n",
    "            if c not in p.child:\n",
    "                return word\n",
    "            p = p.child[c]\n",
    "            if p.isEnd:\n",
    "                return word[:(i+1)]\n",
    "        return word\n",
    "\n",
    "class Solution:\n",
    "    def replaceWords(self, dictionary: List[str], sentence: str) -> str:\n",
    "        aTire = Trie()\n",
    "        for word in dictionary:\n",
    "            aTire.add(word)\n",
    "        \n",
    "        res = []\n",
    "        for word in sentence.split(\" \"):\n",
    "            temp = aTire.matchPrefix(word)\n",
    "            res.append(temp)\n",
    "        return \" \".join(res)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class dicttree:\n",
    "    def __init__(self,):\n",
    "        self.next = defaultdict(dicttree)\n",
    "        self.f = False  # 表示上一个节点是不是一个前缀\n",
    "\n",
    "class Solution:\n",
    "    def replaceWords(self, dictionary: List[str], sentence: str) -> str:\n",
    "        head = cur = dicttree()\n",
    "        for eles in dictionary:\n",
    "            cur = head\n",
    "            for i, ele in enumerate(eles):\n",
    "                cur = cur.next[ele]\n",
    "                if i == len(eles)-1:\n",
    "                    cur.f = True\n",
    "        s = sentence.split(' ')\n",
    "        ans = []\n",
    "        for eles in s:\n",
    "            cur = head\n",
    "            for i, ele in enumerate(eles):\n",
    "                if ele in cur.next:\n",
    "                    cur = cur.next[ele]\n",
    "                    if cur.f: \n",
    "                        ans.append(eles[:i+1])\n",
    "                        break\n",
    "                else: break\n",
    "            if not cur.f: ans.append(eles)\n",
    "        return ' '.join(ans)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self):\n",
    "        self.children = {}\n",
    "        self.isWord = False\n",
    "\n",
    "    def insert(self, word: str):\n",
    "        current = self\n",
    "        for w in word:\n",
    "            if not current.children.get(w):\n",
    "                current.children[w] = Trie()\n",
    "            current = current.children[w]\n",
    "        current.isWord = True\n",
    "\n",
    "    def query(self, word: str) -> str:\n",
    "        current = self\n",
    "        i = 0\n",
    "        for w in word:\n",
    "            if not current.children.get(w):\n",
    "                return word\n",
    "            current = current.children[w]\n",
    "            i += 1\n",
    "            if current.isWord:\n",
    "                break\n",
    "        return word[:i]\n",
    "\n",
    "class Solution:\n",
    "    def replaceWords(self, dictionary: List[str], sentence: str) -> str:\n",
    "        t = Trie()\n",
    "        for d in dictionary:\n",
    "            t.insert(d)\n",
    "        s = sentence.split(' ')\n",
    "        for i in range(len(s)):\n",
    "            s[i] = t.query(s[i])\n",
    "        return ' '.join(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class TrieNode:\n",
    "    def __init__(self):\n",
    "        self.child = {}\n",
    "        self.isend = None \n",
    "\n",
    "class Trie:\n",
    "    def __init__(self):\n",
    "        self.root = TrieNode()\n",
    "    \n",
    "    def insert(self,word):\n",
    "        cur = self.root\n",
    "        for c in word:\n",
    "            if c not in cur.child:\n",
    "                cur.child[c] = TrieNode()\n",
    "            cur = cur.child[c]\n",
    "        cur.isend = word\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def replaceWords(self, dictionary: List[str], sentence: str) -> str:\n",
    "\n",
    "        trie = Trie()\n",
    "        for word in dictionary:\n",
    "            trie.insert(word)\n",
    "        \n",
    "        sen = sentence.split(' ')\n",
    "        res = []\n",
    "        for s in sen:\n",
    "            cur = trie.root\n",
    "            Flag = True \n",
    "            for c in s:\n",
    "                if c in cur.child:\n",
    "                    cur = cur.child[c]\n",
    "                    if cur.isend:\n",
    "                        res.append(cur.isend)\n",
    "                        Flag = False \n",
    "                        break \n",
    "                else:\n",
    "                    res.append(s)\n",
    "                    Flag = False\n",
    "                    break\n",
    "            if Flag:\n",
    "                res.append(s)\n",
    "            \n",
    "        \n",
    "        return ' '.join(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class TrieNode:\n",
    "    def __init__(self):\n",
    "        self.count = 0 # 表示以该处节点构成的串的个数\n",
    "        self.preCount = 0 # 表示以该处节点构成的前缀的字串的个数\n",
    "        self.children = {}\n",
    "        \n",
    "class Trie:\n",
    "\n",
    "    def __init__(self):\n",
    "        self.root = TrieNode()\n",
    "\n",
    "    def insert(self, word):\n",
    "        node = self.root\n",
    "        for ch in word:\n",
    "            if ch not in node.children:\n",
    "                node.children[ch] = TrieNode()\n",
    "            node = node.children[ch]\n",
    "            node.preCount += 1\n",
    "        node.count += 1\n",
    "\n",
    "    def search(self, word):\n",
    "        s = \"\"\n",
    "        node = self.root\n",
    "        for ch in word:\n",
    "            s += ch\n",
    "            if ch not in node.children:\n",
    "                return \"\"\n",
    "            node = node.children[ch]\n",
    "            if node.count > 0: return s\n",
    "                \n",
    "        return \"\"\n",
    "                \n",
    "    def startsWith(self, prefix):\n",
    "        node = self.root\n",
    "        for ch in prefix:\n",
    "            if ch not in node.children:\n",
    "                return False\n",
    "            node = node.children[ch]\n",
    "        return node.preCount > 0\n",
    "\n",
    "class Solution:         \n",
    "    def replaceWords(self, dictionary: List[str], sentence: str) -> str:\n",
    "        trie = Trie()\n",
    "        for word in dictionary: \n",
    "            trie.insert(word)\n",
    "        \n",
    "        ans = []\n",
    "        sentence = sentence.split(' ')\n",
    "        print(\"SEARCH\", trie.search('baba'))\n",
    "        for word in sentence: \n",
    "            s = trie.search(word)\n",
    "            if s:\n",
    "                ans.append(s)\n",
    "            else:\n",
    "                ans.append(word)\n",
    "        return \" \".join(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "class Node:\n",
    "    def __init__(self):\n",
    "        self.isRoot = False\n",
    "        self.children = defaultdict(Node)\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def replaceWords(self, dictionary: List[str], sentence: str) -> str:\n",
    "        root = Node()\n",
    "        for word in dictionary:\n",
    "            cur = root\n",
    "            for w in word:\n",
    "                cur = cur.children[w]\n",
    "            cur.isRoot = True\n",
    "\n",
    "        words = sentence.split(\" \")\n",
    "        for i, word in enumerate(words):\n",
    "            cur = root\n",
    "            for j, w in enumerate(word):\n",
    "                cur = cur.children.get(w)\n",
    "                if cur and cur.isRoot:\n",
    "                    words[i] = word[:j+1]\n",
    "                    break\n",
    "                elif cur == None:\n",
    "                    break\n",
    "        return \" \".join(words)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Node:\n",
    "    def __init__(self):\n",
    "        self.nxt = defaultdict(Node)\n",
    "        self.word = ''\n",
    "\n",
    "class Solution:\n",
    "    def replaceWords(self, dictionary: List[str], sentence: str) -> str:\n",
    "        root = Node()\n",
    "        for s in dictionary:\n",
    "            cur = root\n",
    "            for c in s: cur = cur.nxt[c]\n",
    "            cur.word = s\n",
    "\n",
    "        ans = []\n",
    "        for s in sentence.split():\n",
    "            cur = root\n",
    "            ok = False\n",
    "            for c in s:\n",
    "                if c not in cur.nxt:\n",
    "                    ans.append(s)\n",
    "                    ok = True\n",
    "                    break\n",
    "                cur = cur.nxt[c]\n",
    "                if cur.word:\n",
    "                    ans.append(cur.word)\n",
    "                    ok = True\n",
    "                    break\n",
    "            if not ok:\n",
    "                ans.append(s)\n",
    "        return ' '.join(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Node:\n",
    "    def __init__(self): \n",
    "        self.child = defaultdict(Node)\n",
    "        self.isEnd = False  \n",
    "\n",
    "class Solution: \n",
    "    def insert(self, s:str, root): \n",
    "        node = root \n",
    "        for c in s: \n",
    "            node = node.child[c] \n",
    "        node.isEnd = True \n",
    "    \n",
    "    def check(self, s:str, root): \n",
    "        node = root \n",
    "        pre = \"\" \n",
    "        for c in s: \n",
    "            if c not in node.child:  break\n",
    "            pre += c \n",
    "            node = node.child[c]\n",
    "            if node.isEnd:  return pre \n",
    "        return None \n",
    "\n",
    "    def replaceWords(self, dictionary: List[str], sentence: str) -> str:\n",
    "        trie = Node() \n",
    "        for d in dictionary: \n",
    "            self.insert(d, trie) \n",
    "        ans = \"\" \n",
    "        i, N = 0, len(sentence) \n",
    "        while i<N: \n",
    "            s = \"\" \n",
    "            while i<N and sentence[i] != ' ': \n",
    "                s += sentence[i]\n",
    "                i += 1\n",
    "            pre = self.check(s, trie) \n",
    "            if pre: \n",
    "                ans += pre \n",
    "            else: \n",
    "                ans += s \n",
    "            i += 1\n",
    "            ans += ' ' if i<N else '' \n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self):\n",
    "        \"\"\"\n",
    "        Initialize your data structure here.\n",
    "        \"\"\"\n",
    "        self.array=[None]*26\n",
    "        self.isEnd=False\n",
    "\n",
    "    def insert(self,word):\n",
    "        T=self\n",
    "        for w in word:\n",
    "            index=ord(w)-ord('a')\n",
    "            if not T.array[index]:\n",
    "                T.array[index]=Trie()\n",
    "            T=T.array[index]\n",
    "        T.isEnd=True\n",
    "\n",
    "class Solution:\n",
    "    def replaceWords(self, dictionary: List[str], sentence: str) -> str:\n",
    "        result=[]\n",
    "        T1=Trie()\n",
    "        for word in dictionary:\n",
    "            T1.insert(word)\n",
    "\n",
    "        sen_list=sentence.split(' ')\n",
    "\n",
    "        for sen in sen_list:\n",
    "            T=T1\n",
    "            n=len(result)\n",
    "            for i, s in enumerate(sen):\n",
    "                pos = ord(s) - ord('a')\n",
    "                if not T.array[pos]:\n",
    "                    result.append(sen)\n",
    "                    break\n",
    "                T = T.array[pos]\n",
    "                if T.isEnd:\n",
    "                    result.append(sen[:i+1])\n",
    "                    break\n",
    "            if n==len(result):\n",
    "                result.append(sen[:i+1])\n",
    "\n",
    "\n",
    "        return ' '.join(result)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Pretree:\n",
    "    def __init__(self):\n",
    "        self.children = [None] * 26\n",
    "        self.isEnd = False\n",
    "    \n",
    "    def insert(self, word):\n",
    "        node = self\n",
    "        for ch in word:\n",
    "            ch = ord(ch) - ord('a')\n",
    "            if node.children[ch] is None:\n",
    "                node.children[ch] = Pretree()\n",
    "            node = node.children[ch]\n",
    "            \n",
    "        node.isEnd = True\n",
    "    \n",
    "    def search_prefix(self, word):\n",
    "        node = self\n",
    "        for i, ch in enumerate(word):\n",
    "            ch = ord(ch) - ord('a')\n",
    "            if node.isEnd is True:\n",
    "                return word[:i]\n",
    "            if node.children[ch] is None:\n",
    "                return None\n",
    "            node = node.children[ch]\n",
    "        return None\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def replaceWords(self, dictionary: List[str], sentence: str) -> str:\n",
    "        word_list = sentence.strip().split()\n",
    "\n",
    "        # for idx, word in enumerate(word_list):\n",
    "        #     tree = Pretree()\n",
    "        #     tree.insert(word)\n",
    "        #     min_len = float('inf')\n",
    "        #     for pre in dictionary:\n",
    "        #         if tree.search_prefix(pre) is True and len(pre) < min_len:\n",
    "        #             word_list[idx] = pre\n",
    "        #             min_len = len(pre)\n",
    "        \n",
    "        # return ' '.join(word_list)\n",
    "\n",
    "        tree = Pretree()\n",
    "        for pre in dictionary:\n",
    "            tree.insert(pre)\n",
    "        \n",
    "        for i, word in enumerate(word_list):\n",
    "            ret = tree.search_prefix(word)\n",
    "            if ret is None:\n",
    "                continue\n",
    "            word_list[i] = ret\n",
    "\n",
    "        return ' '.join(word_list)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self):\n",
    "        self.children = [None]*26\n",
    "        self.isEnd = False\n",
    "    \n",
    "    def insert(self, word):\n",
    "        node = self\n",
    "        for w in word:\n",
    "            i = ord(w) - ord(\"a\")\n",
    "            if not node.children[i]:\n",
    "                node.children[i] = Trie()\n",
    "            node = node.children[i]\n",
    "        node.isEnd = True\n",
    "    \n",
    "\n",
    "    def search(self, word):\n",
    "        node = self\n",
    "        for w in word:\n",
    "            i = ord(w) - ord(\"a\")\n",
    "            if not node.children[i]:\n",
    "                return False\n",
    "            node = node.children[i]\n",
    "        if node.isEnd:\n",
    "            return True\n",
    "        return False\n",
    "\n",
    "\n",
    "    def startWith(self, prefix):\n",
    "        node = self\n",
    "        for w in prefix:\n",
    "            i = ord(w) - ord(\"a\")\n",
    "            if not node.children[i]:\n",
    "                return False\n",
    "            node = node.children[i]\n",
    "        return True\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def replaceWords(self, dictionary: List[str], sentence: str) -> str:\n",
    "        trie = Trie()\n",
    "        for dic in dictionary:\n",
    "            trie.insert(dic)\n",
    "        tokens = sentence.split(\" \")\n",
    "        ans = []\n",
    "        for word in tokens:\n",
    "            flag = True\n",
    "            for i in range(1, len(word) + 1):\n",
    "                if trie.search(word[0: i]):\n",
    "                    ans.append(word[0: i])\n",
    "                    flag = False\n",
    "                    break\n",
    "            if flag:\n",
    "                ans.append(word)\n",
    "            \n",
    "        return \" \".join(ans)\n",
    "\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
